Many search engine services, such as Google and Overture, provide for searching for information that is accessible via the Internet. These search engine services allow users to search for display pages, such as web pages, that may be of interest to users. After a user submits a search request (i.e., a query) that includes search terms, the search engine service identifies web pages that may be related to those search terms. To quickly identify related web pages, the search engine services may maintain a mapping of keywords to web pages. This mapping may be generated by “crawling” the web (i.e., the World Wide web) to identify the keywords of each web page. To crawl the web, a search engine service may use a list of root web pages to identify all web pages that are accessible through those root web pages. The keywords of any particular web page can be identified using various well-known information retrieval techniques, such as identifying the words of a headline, the words supplied in the metadata of the web page, the words that are highlighted, and so on. The search engine service may generate a relevance score to indicate how relevant the information of the web page may be to the search request based on the closeness of each match. The search engine service then displays to the user links to those web pages in an order that is based on a ranking that may be determined by their relevance, popularity, importance, and some other measure.
These search engine services, however, may not be particularly useful in certain situations. In particular, it can be difficult to formulate a suitable search request that effectively describes the needed information. For example, if a person sees a historical building or a famous sculpture, the person after returning home may formulate a search request such as “historical building near the James River” or “sculpture of soldier on horse” in hopes of finding more information about the building or sculpture. Unfortunately, the search result may identify so many web pages that it may be virtually impossible for the person to locate relevant information even assuming that the person can accurately remember the details of the building or the sculpture. If the person has a mobile device, such as a personal digital assistant (“PDA”) or cell phone, the person may be able to submit the search request while near the building or the sculpture. Such mobile devices, however, have limited input and output capabilities, which make it both difficult to enter the search request and to view the search result, which may include links to hundreds of web pages.
If the person, however, is able to take a picture of the building or sculpture, the person may then be able to use a Content Based Information Retrieval (“CBIR”) system to find a similar looking picture. Unfortunately, CBIR systems cannot perform fine-grain image matching that is sufficient to effectively identify pictures of the same object (e.g., building or sculpture). Other systems that use local features have achieved satisfying results in object recognition and duplicate images detection. Since an image may have hundreds and thousands of salient points that are represented by local features, a system that uses such local features may have to process features for millions of salient points. Such processing is too computationally expensive to be practical for object recognition and duplicate image detection by an image search engine service.